package com.mj.Heap;

import com.mj.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @Author: LDeng
 * @Date: 2021-03-17 16:00
 */
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {

    private E[] elements;
    private int size;
    private Comparator<E> comparator;
    private static final int DEFAULT_CAPACITY=10;



    public BinaryHeap(){
        this(null,null);
    }

    public BinaryHeap(E[] elements){
        this(elements,null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        this(null,comparator);
    }

    public BinaryHeap(E[] elements,Comparator<E> comparator){
        super(comparator);
        if(elements==null||elements.length==0){
            this.elements=(E[])new Object[DEFAULT_CAPACITY];
        }else{
            size=elements.length;
            int capacity=Math.max(elements.length,DEFAULT_CAPACITY);
            this.elements=(E[])new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i]=elements[i];//数值拷贝， 不能直接赋值，防止外面修改数组内容引起内部变化
            }
            heapify();
        }
    }

    //根据数组批量建堆
    private void heapify() {
        //自上而下的上滤, 效率低
//        for (int i = 1; i <size ; i++) {
//            siftUp(i);
//        }
        //自下而上的下滤
        for (int i = (size>>1)-1; i >=0; i--) {
            siftDown(i);
        }



    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void clear() {
        size=0;
        for (int i = 0; i < size; i++) {
            elements[i]=null;
        }
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size+1);
        elements[size]=element;
        size++;
        siftUp(size-1);
    }

    //获取根元素， 最大值
    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    //删除堆顶元素并返回
    @Override
    public E remove() {
        emptyCheck();
        //用最后一个位置的值覆盖0位置的值
        E root=elements[0];
        elements[0]=elements[size-1];
        elements[size-1]=null;
        size--;
        //下滤
        siftDown(0);
        return root;
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        E root=null;
        if(size==0) {//堆为空， 第一个元素
            elements[0]=element;
            size++;
        }else{//有东西可以替代
            root=elements[0];
            elements[0]=element;//0位置替换为element
            //下滤
            siftDown(0);
        }
        return root;
    }

    private void emptyCheck(){
        if(size==0){
            throw new IndexOutOfBoundsException("Heap is Empty");
        }
    }

    private void elementNotNullCheck(E element){
        if(element==null){
            throw new IllegalArgumentException("element must not be null");
        }
    }

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;

        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;

        System.out.println(oldCapacity + "扩容为" + newCapacity);
    }

    //从index索引开始上滤
    private void siftUp(int index){
//        E e=elements[index];
//        while (index>0){
//            int pindex=(index-1)/2;//(index-1)>>1, 默认向下取整
//            E p=elements[pindex];
//            if(compare(e,p)<=0) return;//自身小于等于父节点
//            //自身大于父节点, 交换index和pindex的内容
//            E tmp=elements[index];
//            elements[index]=elements[pindex];
//            elements[pindex]=tmp;
//            //将pindex值赋值给index 进入下一个循环
//            index=pindex;
//        }

        E element=elements[index];
        while (index>0){
            int parentIndex=(index-1)/2;//(index-1)>>1, 默认向下取整
            E parent=elements[parentIndex];
            if(compare(element,parent)<=0) break;//自身小于等于父节点
            //将父元素存储在index位置, 一次交换即可， 不需要用temp中转
            elements[index] =parent;
            //将pindex值赋值给index 进入下一个循环
            index=parentIndex;
        }
        elements[index]=element;
    }

    private void siftDown(int index){
        E element=elements[index];
        //第一个非叶子节点索引= 非叶子节点的数量=floor(n/2)
        //index<第一个叶子节点的索引， 以后的节点都是叶子节点
        int half=size>>1;
        while (index<half){
            //由于是完全二叉树，index的节点有两种情况
            //1. 只有左子节点
            //2. 同时有两个节点
            //默认为左子节点的索引
            int childIndex=(2*index)+1;
            E child=elements[childIndex];
            //右子节点
            int rightIndex=childIndex+1;
            //选出左右子节点最大的
            if(rightIndex<size&&compare(elements[rightIndex],child)>0){
                childIndex=rightIndex;
                child=elements[rightIndex];
            }
            if(compare(element,child)>=0) break;
            //将子节点存放到index位置
            elements[index]=child;
            //重新设置index
            index=childIndex;
        }
        elements[index]=element;
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        Integer index= (Integer) node;
        index=2*index+1;
        return index>=size?null:index;
    }

    @Override
    public Object right(Object node) {
        Integer index= (Integer) node;
        index=2*index+2;
        return index>=size?null:index;
    }

    @Override
    public Object string(Object node) {
        Integer index= (Integer) node;
        return elements[index];
    }
}
